/*
 * @Author: szx
 * @Date: 2022-04-28 13:25:45
 * @LastEditTime: 2022-04-28 14:00:20
 * @Description:
 * @FilePath: \leetcode\剑指offerII\096\096.js
 */

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function (s1, s2, s3) {
    const len1 = s1.length,
        len2 = s2.length,
        len3 = s3.length;
    if (len1 + len2 !== len3) return false;
    const dp = new Array(len1 + 1).fill(false).map(() => new Array(len2 + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i < len1; i++) dp[i + 1][0] = dp[i][0] && s3[i] == s1[i];
    for (let j = 0; j < len2; j++) dp[0][j + 1] = dp[0][j] && s3[j] == s2[j];
    for (let i = 0; i < len1; i++) {
        for (let j = 0; j < len2; j++) {
            const m = i + j + 1;
            dp[i + 1][j + 1] = (dp[i][j + 1] && s1[i] == s3[m]) || (dp[i + 1][j] && s2[j] == s3[m]);
        }
    }
    return dp[len1][len2];
};
